"""
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
"""
def dfs(nums, depth, path, used, res):
    # 已经到了叶子节点
    if(depth == len(nums)):
        res.append(path.copy())
        return
    for i in range(len(nums)):
        if used[i] or (i > 0 and used[i - 1] == False and nums[i] == nums[i - 1]):
            continue
        # 还没被选过
        path.append(nums[i])
        used[i] = True
        dfs(nums, depth + 1, path, used, res)
        # 回溯
        path.pop()
        used[i] = False



class Solution:

    def permuteUnique(self, nums):
        path = []
        used = []
        depth = 0
        res = []
        for _ in range(len(nums)):
            used.append(False)
        if len(nums) == 0:
            return res
        nums.sort()
        dfs(nums, depth, path, used, res)
        return res


# print(Solution.permuteUnique(self=None, nums=[3,3,0,3]))